package history

import (
	"strconv"
	"strings"
)

/**
 * @Description:394. 字符串解码 实现 String s = "1[a]2[c]3[d]";输出为accddd String s1 = "3[a2[c]]"; 输出为accaccacc
 * @Keyword: 栈/递归
 * @Author: kami
 * @Date: 2022/2/9 22:55
 **/
func decodeStringStack(s string) string {
	var stk []string
	ptr := 0
	for ptr < len(s) {
		cur := s[ptr]
		if cur >= '0' && cur <= '9' {
			digits := getDigits(s, &ptr)
			stk = append(stk, digits)
		} else if (cur >= 'a' && cur <= 'z' || cur >= 'A' && cur <= 'Z') || cur == '[' {
			stk = append(stk, string(cur))
			ptr++
		} else {
			ptr++
			var sub []string
			for stk[len(stk)-1] != "[" {
				sub = append([]string{stk[len(stk)-1]}, sub...)
				stk = stk[:len(stk)-1]
			}
			// 去掉 [
			stk = stk[:len(stk)-1]
			// 获取重复次数
			repTime, _ := strconv.Atoi(stk[len(stk)-1])
			stk = stk[:len(stk)-1]
			t := strings.Repeat(getString(sub), repTime)
			stk = append(stk, t)
		}
	}
	return getString(stk)
}

var (
	src string
	ptr int
)

func decodeStringDfs(s string) string {
	src = s
	ptr = 0
	return getStringDfs()
}

func getStringDfs() string {
	if ptr == len(src) || src[ptr] == ']' {
		return ""
	}
	cur := src[ptr]
	repTime := 1
	ret := ""
	if cur >= '0' && cur <= '9' {
		repTime = getDigitsDfs()
		ptr++
		str := getStringDfs()
		ptr++
		ret = strings.Repeat(str, repTime)
	} else if cur >= 'a' && cur <= 'z' || cur >= 'A' && cur <= 'Z' {
		ret = string(cur)
		ptr++
	}
	return ret + getStringDfs()
}
func getDigitsDfs() int {
	ret := 0
	for ; src[ptr] >= '0' && src[ptr] <= '9'; ptr++ {
		ret = ret*10 + int(src[ptr]-'0')
	}
	return ret
}

func getDigits(s string, ptr *int) string {
	ret := ""
	for ; s[*ptr] >= '0' && s[*ptr] <= '9'; *ptr++ {
		ret += string(s[*ptr])
	}
	return ret
}

func getString(v []string) string {
	ret := ""
	for _, s := range v {
		ret += s
	}
	return ret
}

/*
井英公司面试
1. 快速排序
2. 查找两个数组中的不重复的数字
3. 写一个通用的方案，入参为id列表，支持查询不同的数据库表，并且按照入参id顺序返回modle
*/
func quickSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	quickSortNums(nums, 0, len(nums)-1)
	return nums
}

func quickSortNums(nums []int, left, right int) {
	if left >= len(nums) || right < 0 || left >= right {
		return
	}

	var start = left
	var end = right
	var povitVal = nums[start]
	for start < end {
		for start < end && nums[end] > povitVal {
			end--
		}
		if start < end {
			nums[start] = nums[end]
			start++
		}

		for start < end && nums[start] < povitVal {
			start++
		}
		if start < end {
			nums[end] = nums[start]
			end--
		}

	}
	nums[start] = povitVal
	quickSortNums(nums, left, start-1)
	quickSortNums(nums, start+1, right)
}

func findDiffNums(nums1, nums2 []int) []int {
	var seenMap = make(map[int]bool)
	for i := 0; i < len(nums1); i++ {
		seenMap[nums1[i]] = true
	}
	var res []int
	for i := 0; i < len(nums2); i++ {
		if seenMap[nums2[i]] {
			delete(seenMap, nums2[i])
			continue
		}
		res = append(res, nums2[i])
	}
	for key, _ := range seenMap {
		res = append(res, key)
	}
	return res
}

type dbModel struct {
	name string
}

type model interface {
	GetStruct() dbModel
	GetResults() []dbModel
}

func findByIds(ids []int, t model) []model {
	return nil
}
